//https://leetcode.cn/problems/rotated-digits/submissions/575096557/

int diffs[10] = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};

class Solution {
public:
    int rotatedDigits(int n) {
        auto s = to_string(n); // 将 n 转换为字符串，方便逐位处理
        int m = s.length(), dp[m][2]; // dp[i][2] 表示第 i 位时是否包含好数
        memset(dp, -1, sizeof(dp)); // 初始化记忆化数组，初始值为 -1 表示未计算过

        // 定义递归函数 f，使用 lambda 表达式
        function<int(int, bool, bool)> f = [&](int i, bool has_diff, bool is_limit) -> int {
            if (i == m) return has_diff; // 当处理到末尾时，如果包含好数则返回 1，否则返回 0
            if (!is_limit && dp[i][has_diff] >= 0) return dp[i][has_diff]; // 如果不受限制且已计算过，直接返回结果
            int res = 0;
            int up = is_limit ? s[i] - '0' : 9; // 当前位的上限，如果受限则为 s[i]，否则为 9
            for (int d = 0; d <= up; ++d) { // 枚举当前位要填入的数字 d
                if (diffs[d] != -1) { // d 不能是 3, 4, 7，因为这些数字无效
                    res += f(i + 1, has_diff || diffs[d], is_limit && d == up); // 递归处理下一位
                }
            }
            if (!is_limit) dp[i][has_diff] = res; // 记忆化保存结果
            return res;
        };
        return f(0, false, true); // 从第 0 位开始递归，初始状态未包含好数，受限于 n
    }
};